package day29;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[]arr=new int[]{3,1,2};
        solution.getFirstUnFormedNum(arr);
    }
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
	public int getFirstUnFormedNum(int[] arr) {
        //递归+求极值
        int min=Integer.MAX_VALUE;
        int sum=0;
        //循环求最小值
        for(int i=0;i<arr.length;++i){
            if(arr[i]<min){
                min=arr[i];
            }
        }
         //求和
            for(int i=0;i<arr.length;++i){
                sum+=arr[i];
            }
        //递归
        int res=min;
        int[]ans=new int[sum+2];
        reverse(arr,0,0,ans);
        //最后遍历求结果
        for(int i=min;i<ans.length;++i){
            if(ans[i]==0){
                return i;
            }
        }
        return -1;

	}
    public void reverse(int[]arr,int index,int sum,int[]ans){
        if(index>=arr.length){
            ans[sum]=1;
            return;
        }
        //结果累加
        ans[sum]=1;
        //递归
        reverse(arr,index+1,sum,ans);
        reverse(arr,index+1,sum+arr[index],ans);
        
    }
}